package java.com.mjx.algorithm;

/**
 * 二分查找
 * Created by 梅京翔 on 2017 01 17上午 12:34.
 */
public class BinarySearch {
    public static int search(Integer[] array,Integer key){
        int lower=0;
        int upper=array.length-1;
        int cur;
        while (true){
            cur=(lower + upper)/2;
            if (array[cur] == key)
                return cur;
            else if (lower > upper)
                return -1;
            else {
                if (array[cur] > key)
                    upper = cur - 1;
                else
                    lower = cur + 1;
            }
        }
    }

    public static void init(Integer[] array){
        for (int i = 0; i < array.length; i++) {
            array[i]=new Integer(i+1);
        }
    }

    public static void main(String[] args) {
        Integer[] testArray=new Integer[999999];
        init(testArray);
        long start=System.currentTimeMillis();
//        System.out.println(search(testArray,10));
        System.out.println(search(testArray,99));//找不到的情况
        long end=System.currentTimeMillis();
        System.out.println((end - start));
    }
}
